package searcher;

import java.util.*;

/**
 * a class to do some set operation in somewhat quick way
 * each set should be organized in a small-up-large-bottom manner to ensure the correctness
 * so should the difference set in the difference() method
 * 
 * after using it in file number set operation, i find it may also work in some other situation
 * the name of the class is largely confused when i use it to do some other work 
 * 
 * last thing, believe me, it is not so good
 * because it is me that invented all the algorithm
 * (still worse, i had a bad cold when doing this)
 * @author shitgao
 *
 */

public class FileNumSet {
	private Vector<Vector<Integer>> sets;
	private Vector<FileNumSetElem> result;
	
	public FileNumSet (Vector<Vector<Integer>> sets){
		this.sets=sets;
		result=null;
	}
	
	public FileNumSet (){
		sets=null;
		result=null;
	}
	
	public void resetSets (Vector<Vector<Integer>> sets){
		this.sets=sets;
	}
	
	public Vector<FileNumSetElem> getResults () {
		return result;
	}
	
	public void union (){
		if (sets==null || sets.size()==0){
			result=null;
			return;
		}
			
		int lastreturn,source;
		result=new Vector<FileNumSetElem>();
		HeapElem he;
		MinHeap<HeapElem> mh= new MinHeap<HeapElem>();
		Vector<Integer> pos=new Vector<Integer>(sets.size());
		for (int i=0;i<sets.size();i++){
			pos.add(1);
			if (sets.get(i)!=null){
				he=new HeapElem(sets.get(i).get(0),i);
				mh.addWithOrder(he);
			}
		}
		lastreturn=-1;
		while (mh.size()>0){
			he=mh.removeWithOrder();
			source=he.getsourceSet();
			if (he.getFileNum()!=lastreturn){
				result.add(new FileNumSetElem(he.getFileNum(),source));
				lastreturn=he.getFileNum();
			}
			else{
				result.get(result.size()-1).addAppear(source);
			}
			if (pos.get(source)<sets.get(source).size()){
				he=new HeapElem(sets.get(source).get(pos.get(source)),source);
				pos.set(source, pos.get(source)+1);
				mh.addWithOrder(he);
			}
		}
	}
	
	public void intersection (){
		if (sets==null || sets.size()==0){
			result=null;
			return;
		}
		for (int i=0;i<sets.size();i++){
			if (sets.get(i)==null){
				result=null;
				return;
			}
		}
		result=new Vector<FileNumSetElem>();
		Vector<Integer> pos=new Vector<Integer>(sets.size());
		int size=sets.size();
		int max=-1;
		int conum=0;
		int pt=0;
		boolean flag=true;
		boolean flagin;
		for (int i=0;i<size;i++){
			pos.add(0);
			if (sets.get(i).get(0)>max){
				max=sets.get(i).get(0);
				conum=1;
			}
			else if (sets.get(i).get(0)==max){
				conum++;
			}
		}
		
		while (flag){
			flagin=false;
			while (pos.get(pt)<sets.get(pt).size() && sets.get(pt).get(pos.get(pt))<max ){
				pos.set(pt,pos.get(pt)+1);
				flagin=true;
			}
			if (pos.get(pt)>=sets.get(pt).size()){
				flag=false;
			}
			else{
				if (sets.get(pt).get(pos.get(pt))==max){
					if (flagin)
						conum=conum+1;
					if (conum==size){
						result.add(new FileNumSetElem(max));
						pos.set(pt,pos.get(pt)+1);
						if (pos.get(pt)<sets.get(pt).size()){
							max=sets.get(pt).get(pos.get(pt));
							conum=1;
						}
						else 
							flag=false;
					}
						
				}
				else if (sets.get(pt).get(pos.get(pt))>max){
					max=sets.get(pt).get(pos.get(pt));
					conum=1;
				}
				pt=pt+1;
				if (pt>=size)
					pt=0;
			}	
		}
	}
	
	public void differenceWith(Vector<FileNumSetElem> setin){
		if (setin==null || result==null || result.size()==0 || setin.size()==0)
			return;
		Vector<Integer> diffset=new Vector<Integer>(setin.size());
		for (int i=0;i<setin.size();i++)
			diffset.add(setin.get(i).getKey());
		difference(diffset);
	}
	
	public void difference(Vector<Integer> diffset){
		if (result==null || diffset==null || result.size()==0 || diffset.size()==0)
			return;
		int posthis=0;
		int posdiff=0;
		int sizethis=result.size();
		int sizediff=diffset.size();
		boolean flag=true;
		Vector<Boolean> delflag=new Vector<Boolean>(sizethis);
		for (int i=0;i<sizethis;i++)
			delflag.add(false);
		while (flag){
			if (result.get(posthis).getKey()<diffset.get(posdiff)){
				posthis++;
				if (posthis==sizethis)
					flag=false;
			}
			else if (result.get(posthis).getKey()>diffset.get(posdiff)){
				posdiff++;
				if (posdiff==sizediff)
					flag=false;
			}
			else if (result.get(posthis).getKey()==diffset.get(posdiff)){
				delflag.set(posthis, true);
				posdiff++;
				posthis++;
				if (posdiff==sizediff || posthis==sizethis)
					flag=false;
			}
		}
		for (int i=sizethis-1;i>=0;i--)
			if (delflag.get(i))
				result.remove(i);
	}
	
	//this.mergeWith(that)
	//if a elem exists in this, look if it also exists in that
	//if it does, merge the "appears" together
	//but at this moment, it is designed for some special use,
	//so the implementation is simplified
	public void mergeWith (Vector<FileNumSetElem> setin){
		if (result==null || setin==null || result.size()==0 || setin.size()==0)
			return;
		int posthis=0;
		int posthat=0;
		int sizethis=result.size();
		int sizethat=setin.size();
		boolean flag=true;
		while (flag){
			if (result.get(posthis).getKey()<setin.get(posthat).getKey()){
				posthis++;
				if (posthis==sizethis)
					flag=false;
			}
			else if (result.get(posthis).getKey()>setin.get(posthat).getKey()){
				posthat++;
				if (posthat==sizethat)
					flag=false;
			}
			else {
				//here some simplification occurs
				result.set(posthis, new FileNumSetElem(setin.get(posthat).getKey(),setin.get(posthat).getAppears()));
				posthis++;
				posthat++;
				if (posthis==sizethis || posthat==sizethat)
					flag=false;
			}
		}
	}
	
	//return the least length of sections containing at least one number of each set
	//this method has nothing to do with file numbers
	//it is really used in ranking
	//however, i just implement it here for simplification
	//everyone who unfortunately reads my code should be awared that i am such a lazy fat man
	public int leastCover(){
		MinHeap<HeapElem> mh=new MinHeap<HeapElem>();  
		//actually, i used the heap to sort, any kind of sorting can be used here
		int size=sets.size();
		int covered=0;
		Vector<Integer> num=new Vector<Integer>(size);
		int leastlength=831217;  //my birth day, if you wonder what is this number
		HeapElem he;
		Vector<Integer> vec;
		Vector<HeapElem> queue=new Vector<HeapElem>();
		boolean flag=true;
		for (int i=0;i<sets.size();i++){
			num.add(0);
			vec=sets.get(i);
			for (int j=0;j<vec.size();j++){
				he=new HeapElem(vec.get(j),i);
				mh.addWithOrder(he);
			}
		}
		while (flag){
			if (mh.size()==0)
				flag=false;
			else{
				he=mh.removeWithOrder();
				queue.add(he);
				//System.out.println(he.getFileNum()+" is added");
				num.set(he.getsourceSet(), num.get(he.getsourceSet())+1);
				if (num.get(he.getsourceSet())==1){
					covered++;
					if (covered==size){
						int temp;
						boolean iscal=false;
						if (num.get(queue.get(0).getsourceSet())==1){
							temp=queue.get(queue.size()-1).getFileNum()
								-queue.get(0).getFileNum();
							if (temp<leastlength)
								leastlength=temp;
							iscal=true;
						}
						he=queue.remove(0);
						//System.out.println(he.getFileNum()+" is removed");
						num.set(he.getsourceSet(), num.get(he.getsourceSet())-1);
						if (num.get(he.getsourceSet())==0)
							covered--;
						while (queue.size()>0 && num.get(queue.get(0).getsourceSet())>1){
							int temp1=queue.get(0).getsourceSet();
							num.set(temp1, num.get(temp1)-1);
							he=queue.remove(0);
							//System.out.println(he.getFileNum()+" is removed");
						}
						if (!iscal){
							temp=queue.get(queue.size()-1).getFileNum()
								-queue.get(0).getFileNum();
							if (temp<leastlength)
								leastlength=temp;
						}
					}
				}
			}
		}
		return leastlength;
	}
}
